import java.lang.reflect.Array;
import java.util.*;

public class PrimAndKruskal {
    /**
     * 最小生成树/最小连通图
     */
    public static void main(String[] args) {
        int MAX = Integer.MAX_VALUE;
        int[][] G = {{0, 10, MAX, MAX, MAX, 11, MAX, MAX, MAX},
                {10, 0, 18, MAX, MAX, MAX, 16, MAX, 12},
                {MAX, MAX, 0, 22, MAX, MAX, MAX, MAX, 8},
                {MAX, MAX, 22, 0, 20, MAX, MAX, 16, 21},
                {MAX, MAX, MAX, 20, 0, 26, MAX, 7, MAX},
                {11, MAX, MAX, MAX, 26, 0, 17, MAX, MAX},
                {MAX, 16, MAX, MAX, MAX, 17, 0, 19, MAX},
                {MAX, MAX, MAX, 16, 7, MAX, 19, 0, MAX},
                {MAX, 12, 8, 21, MAX, MAX, MAX, MAX, 0}};

        Prim(G);
        System.out.println("=========================");
        Kruskal(G);
    }


    public static void Prim(int[][] G) {
        int len = G.length;
        int[] adjVex = new int[len];
        int[] lowCost = Arrays.copyOf(G[0], len);
        int sum = 0;
        for (int i = 0; i < len - 1; i++) {
            int min = Integer.MAX_VALUE;
            int k = 0;
            for (int j = 0; j < len; j++) {
                if (lowCost[j] != 0 && lowCost[j] < min) {
                    min = lowCost[j];
                    k = j;
                }
            }
            System.out.println(String.format("%d和%d连接,距离%d", adjVex[k], k, lowCost[k]));
            sum += lowCost[k];
            lowCost[k] = 0;
            for (int j = 0; j < len; j++) {
                if (lowCost[j] != 0 && G[k][j] < lowCost[j]) {
                    lowCost[j] = G[k][j];
                    adjVex[j] = k;
                }
            }
        }
        System.out.println("最短路径" + sum);
    }

    public static void Kruskal(int[][] G) {
        class Edge {
            int begin;
            int end;
            int weight;

            public Edge(int begin, int end, int weight) {
                this.begin = begin;
                this.end = end;
                this.weight = weight;
            }
        }

        int len = G.length;
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (G[i][j] != 0 && G[i][j] < Integer.MAX_VALUE){
                    edges.add(new Edge(i,j,G[i][j]));
                }
            }
        }
        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        int[] parent = new int[len];
        int sum = 0;
        for (Edge edge : edges) {
            int n = find(parent, edge.begin);
            int m = find(parent, edge.end);
            if (n != m){
                parent[n] = m;
                System.out.println(String.format("%d和%d连接,距离%d", edge.begin, edge.end, edge.weight));
                sum += edge.weight;
            }
        }
        System.out.println("最短路径" + sum);
    }
    public static int find(int[] parent, int f){
        while (parent[f] != 0){
            f = parent[f];
        }
        return f;
    }
}
